home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 18331 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: ix.netcom.com!news
  2. From: Bradd W. Szonye <bradds@ix.netcom.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: RE: Help for integer multiplication???
  5. Date: 19 Apr 1996 09:33:04 GMT
  6. Organization: Netcom
  7. Message-ID: <01bb2dd3.80300280$c6c2b7c7@Zany.localhost>
  8. References: <96090.202303IO92118@MAINE.MAINE.EDU> <4jnabd$a5k@news.microsoft.com>
  9. NNTP-Posting-Host: det-mi6-06.ix.netcom.com
  10. X-NETCOM-Date: Fri Apr 19  4:33:04 AM CDT 1996
  11. X-Newsreader: Microsoft Internet News
  12.  
  13.  
  14. On Sunday, March 31, 1996, Dann Corbit wrote...
  15. > In article <96090.202303IO92118@MAINE.MAINE.EDU>,
  16. IO92118@MAINE.MAINE.EDU says...
  17. > >
  18. > >Hi:
  19. > >I want to write a program to do integer multiplication.
  20. > int int_multiply( int i, int j)
  21. > {
  22. >    return i*j;
  23. > }
  24. > 
  25. > >1101 1110 1010 0001
  26. > >1010 1101 0010 1010
  27. > >-------------------
  28. > >
  29. > >for normal method, it's time complexity is n square.
  30. > >
  31. > >if I devide it into two parts.
  32. > >2**(n/2)*1101 1110 + 1010 0001
  33. > >2**(n/2)*1010 1101 + 0010 1010   this is 3**(log(n)) much faster.
  34. > >-------------------------------
  35. > >** means to the power. exactly 2**(n/2) mean shift.
  36. > >
  37. > >If I want to a program, how to represent 1101 1110 1010 0001 ???
  38. > >Can I just decimal number or not, or something else???
  39. > >
  40. > >Thank you very much!!!
  41. > I assume you want to look into something more than a simple
  42. > integer multiply.
  43. > 
  44. > See "Desigm Strategies for Optimal Multiplier Circuits" by
  45. > Charles Martel, Vokin Oklobdzija, R. Ravi, Paul F. Sterling
  46. > in the Proceedings: 12th Symposium on Computer Arithmatic.
  47. > This is by the IEEE.
  48.  
  49. Another good source, as always, is Don Knuth's "Art of Computer
  50. Programming, Volume II: Seminumerical Methods." The book is expensive,
  51. difficult to read, and 25 years old, but it's still current when it comes
  52. to doing integer math. In theory, you can actually multiply big enough
  53. integers in linear time, and Knuth explains how. (Of course the overhead
  54. is ridiculous, one of those *big* linear constants.)
  55.  
  56.  
  57.